//
// Description: 4. 寻找两个正序数组的中位数
// Created by Loading on 2022/3/13.
//

#include <bits/stdc++.h>

using namespace std;

double findMedianSortedArrays(vector<int> &nums1, vector<int> &nums2) {
    int n = nums1.size();
    int m = nums2.size();

    // 得到合并数组的第 K 小的数
    auto getKth = [&](int k) {
        int start1 = 0;
        int start2 = 0;

        while (true) {
            // 其中一个数组已全部删除，直接返回另一个数组从start开始的第k个值
            if (start1 == n) {
                return nums2[start2 + k - 1];
            }
            if (start2 == m) {
                return nums1[start1 + k - 1];
            }
            // k == 1，直接返回两个数组首元素的较小者
            if (k == 1) {
                return min(nums1[start1], nums2[start2]);
            }

            /* 注意越界情况 */
            // 两个数组的第 k / 2 个元素的下标
            int mid1 = min(start1 + k / 2, n) - 1;
            int mid2 = min(start2 + k / 2, m) - 1;
            // 根据大小更新 k 和起始下标
            if (nums1[mid1] > nums2[mid2]) {
                k -= mid2 - start2 + 1;
                start2 = mid2 + 1;
            } else {
                k -= mid1 - start1 + 1;
                start1 = mid1 + 1;
            }
        }
    };

    if ((n + m) % 2 == 1) {
        return getKth((n + m + 1) / 2);
    } else {
        return (getKth((n + m + 1) / 2) + getKth((n + m + 2) / 2)) / 2.0;
    }
}

int main() {
    vector<int> nums1{2, 3, 5, 6};
    vector<int> nums2{1, 4, 7, 9};
    double res = findMedianSortedArrays(nums1, nums2);
    cout << res << endl;

    return 0;
}